Niekoľko výsledkov z prehľadávania do šírky v M*N hlavolame.

Vieme, že tento hlavolam sa môže nachádzať v ľubovoľnom stave, ktorý patrí práve do jednej z dvoch navzájom disjunktných, rovnako veľkých množín stavov. Ľubovoľný stav vyjadrujú permutácie, takže počet možných stavov, patriacich do jednej z týchto množín je polovica z faktoriálu z M*N. Toto číslo neuveriteľne rýchlo rastie, takže nie je problém zahltiť pamäť počítača a dospieť k nepoužiteľne dlhým časom výpočtu. Nasledujúce príklady riešení (prvé tri) ukazujú, k akým časom sa je možné priblížiť pri aspoň trochu slušnej optimalizácii riešenia. Časy boli určené pre AMD Turion 1,4GHz, 500MB operačnej pamäti, priamo z IDE, pri náročnej hudbe na pozadí (asi 15% výkonu – to boli časy!).

Stavy z uvedených zoznamov je tiež vhodné využiť na testovanie vlastného riešenia. (Môžete skontrolovať, či môj algoritmus fungoval správne a neexistuje kratšia cesta medzi vybranými stavmi.) Tiež je možné využiť, že už viete, v akej najväčšej hĺbke môže byť cieľový uzol.

V prostredí NetBeans, v Jazyku JAVA 1.5, bol naprogramovaný algoritmus prehľadávania celého stavového priestoru do šírky. Oproti pôvodnému, všeobecnému postupu, bolo použitých niekoľko optimalizácií:

1. Algoritmus negeneruje „spätný“ ťah, to znamená, že napríklad ak rodičovský uzol bol vytvorený zo svojho predchodcu posunom políčka doľava, nebude sa generovať jeho potomok posunom doprava. Ušetrí sa tým zbytočné vytváranie uzla a kontrola stavu, ktorý už bol spracovaný.
2. Vytvorené uzly s novými stavmi sú vkladané do frontu, aby sa dodržalo spracovanie prehľadávaním do šírky, ale zároveň sa ich stav ukladá do štruktúry HashSet, aby bola zaistená rýchla kontrola už vytvoreného stavu.
3. Existuje len jediný HashSet všetkých stavov uzlov, spracované uzly na rozdiel od vygenerovaných už nie sú vo fronte. Uzly sú však udržiavané v odkaze na rodiča, aby sme mohli na záver vypísať najdlhšiu nájdenú (optimálnu) cestu.

Výstupy pre rozmer:

3*2;	6! =	720
4*2;	8! =	40 320
3*3;	9! =	362 880
5*2;	10! =	3 628 800
4*3;	12! =	479 001 600
6*2;	12! =	479 001 600

Rozmer 5*2 bol vytvorený takmer o 11 rokov neskôr, na notebooku s procesorom core i7 a 16GB pamäti. Desaťnásobný počet uzlov pre tento rozmer zvládol za približne rovnaký čas ako pôvodný notebook pre rozmer 3x3. Rozmer 4x3 je ale zatiaľ pre Javu priveľký. JVM je 32 bitový, zvláda heap do veľkosti 4GB, kde v pôvodnej verzii dokázal uložiť 12 miliónov uzlov a v novej verzii 25 miliónov uzlov. Rozmer 4x3 však obsahuje 240 miliónov uzlov. Na dosiahnutie hĺbky 29 už Java potrebovala asi tri minúty a viac ako polovicu z toho času bežal Garbage Collector.

Na riešenie hlavolamu s dvanástimi políčkami boli použité ďalšie optimalizácie:

1. Stav hlavolamu je udržiavaný v jednej premennej typu long (64 bitov, použité sú 4 bity na číslo, takže skutočne využitých je len 48 bitov). Odkaz na predchodcu je Int a ešte je tam po Byte na hĺbku, pozíciu nuly a smer, takže veľkosť celého uzla je 16 Byte. (Java však aj tak potrebovala okolo 140 Byte na jeden uzol.)
2. Hashtable obsahuje len uvedený stav, teda hodnoty veľkosti 8 Byte. Pôvodný čas pre rozmer 5x2 bol v jazyku C dve sekundy, ad-hoc optimalizáciou hash funkcie a posunu sa mi podarilo čas stiahnuť na 1,5 sekundy. Výraznejšie skrátenie času prišlo až s kompiláciou na 64-bitovú aplikáciu, lebo väčšina práce sa vykonáva so 64-bitovými číslami.
3. V jazyku C sú uzly ukladané do jedného pamäťového bloku (pre 240 miliónov uzlov vo veľkosti 3,84 GB), ktorý slúži zároveň ako front uzlov. Hashtable je rovnakej veľkosti, takže dochádza maximálne k 50% zaplneniu.

---